The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology.
As used herein, the term “packet” refers to packets of all types, including, but not limited to, fixed length cells and variable length packets. Moreover, these packets may contain one or more types of information, including, but not limited to, voice, data, video, and audio information. Furthermore, the term “system” is used generically herein to describe any number of components, packet switch elements, packet switches, networks, computer and/or communication devices or mechanisms, or combinations thereof.
Consumers and designers of these systems typically desire high reliability and increased performance at a reasonable price. Also, certain users and applications of communications services demand a guaranteed quality of service. To help in this regard, communications systems may meter or police the amount of traffic allowed into a communications component or across a link. For example, a line card might assign and enforce an average traffic rate while accommodating a limited burstiness in the traffic.
A common approach to implement such a metering scheme is through a classic token bucket meter. Tokens are added to a bucket at some fixed rate of X (tokens per second) and are removed from the bucket whenever a packet arrives. A bucket also has a finite depth, as it never contains more than Y tokens. A token might represent the allowance of an entire packet, or might represent some fraction or multiple of a packet (e.g., one byte).
When a packet arrives and the requisite number of tokens are available (e.g., at least one token when a token represents one packet, at least m tokens for an m byte packet when a token represents a byte of information, etc.), the corresponding number of tokens are removed from the bucket and the packet is considered to be conforming (i.e., in profile). If the requisite number of tokens are not in the bucket when the packet arrives, the packet is declared to be non-conforming (i.e., out of profile). The token replenishment rate X represents the long-term average rate limit if packets are to remain conforming. However, packets may arrive in short bursts and still be considered in profile. For example, up to Y tokens may be available in the bucket, and therefore up to Y packets or Y bytes may arrive back to back in time and still get through. Judicious selection of X and Y allows a profile to enforce a desired long-term average packet rate while being tolerant of short bursts of packets arriving faster than X packets or bytes per second, or some variant thereof.
In a typical token bucket implementation, tokens are added to the bucket at the rate X. The step of adding tokens to the bucket is done in response to the arrival of a packet or an expiration of a timer, with the number of tokens added being a function of the current time, the last time tokens were added, and the rate X. In one known implementation, the number of tokens added is calculated by multiplying the rate X by the difference in the time (e.g., current time minus last time, or the interval of the timer). In another known implementation, the number of tokens added is calculated by a division operation of the time interval by the rate, typically to determine a number of elapsed fixed time periods. However, requiring the use of a multiply or divide operation to determine the number of tokens to add can be problematic especially when the processor or component determining the number of tokens to add does not have a built-in multiply or divide operation.
One known approach to avoid the use of a multiply operation uses a shifting operation (i.e., a multiply by two operation). However, this approach suffers from limitations on the rate or update interval, and may result in variances in the number of tokens added when compared to the desired rate caused by such things as truncating and rounding errors. Another known approach uses timers for incrementing the token buckets at fixed time intervals with the number of tokens added being pre-computed token products of the token generation rates and the fixed time intervals; however, managing such timers and incrementing rates across many policing entities in a system is complex and not easily scalable to a very large number of connections and rates.
Needed are new methods and apparatus for implementing a token bucket scheme, especially ones that do not rely on a real-time multiply operation to determine the number of tokens to add to a bucket.